package projet2_ro;

import java.util.ArrayList;

/**
 * This class allows us to regroup elements and their opposite together
 * @author Houdemer and Rigon
 */
public class UFind {
	
	private int pere[];
        private int opposite[];//Chaque case contiendra la valeur de la racine de l'ensemble oppose
        private int indiceEnsemble[];//Chaque case contiendra l'indice dans la liste des ensembles opposes en positif si il est en haut, negatif si il est en bas
        private int soustractions[];
        private ArrayList<ArrayList<Ensemble>> patates;
        /**
         * 
         * @param taille Edge number of the considered graph
         */
	public UFind(int taille){
		pere = new int[taille];
                opposite = new int[taille];
		indiceEnsemble = new int[taille];
                
		for(int i = 0 ; i < taille ; i++){
			pere[i]=-1;
                        opposite[i] = -1;
                        indiceEnsemble[i] = 0;
		}
	}
        
        /**
         * This method unify the sets of opposite variables
         * @param e1 a variable of an equation
         * @param e2 a variable of an equation
         */
        public void unionOpposite(int e1, int e2){
            // Si 2 variables appartiennent au meme ensemble
            // elles ne peuvent pas etre opposees donc le systeme d'equation est faux.
            if(find(e1) == find(e2)){
                System.err.print("ERREUR: Le systeme d'equations est faux.\ne"+e1+" doit etre different de "+e2);
                System.exit(0);
            }

            //Si jamais l'ensemble auquel e2 appartient n'a pas d'oppose
            if(findOpposite(e2) == -1){
                // Si l'ensemble de e1 non plus n'a pas d'oppose
                if(findOpposite(e1) == -1){
                    //Alors on les mets opposes l'un a l'autre
                    opposite[find(e1)] = find(e2);
                    opposite[find(e2)] = find(e1);
                    
                }
                //Si e1 a deja un oppose
                else{
                    int x = findOpposite(e1);
                    // On dit a e2 d'appartenir a l'ensemble oppose a e1
                    union(e2,x);
                }
            }
            // Si e2 a un oppose
            else{
                // Alors dans ce cas-la e1 appartiendra a l'ensemble oppose a e2
                union(e1,findOpposite(e2));
            }   
        }

        /**
         * This functions is used to know if an set has an opposite or not
         * @param element a variable of an equation
         * @return the index of the opposite of the variable's set if there's one, else -1
         */
        public int findOpposite(int element){
            // Si element a un oppose
            if (opposite[find(element)] > -1)
                // On renvoie son oppose
                return opposite[find(element)];
            else
                // Sinon on renvoie -1 car l'element n'as pas d'oppose
                return -1;
        }

        /**
         *
         * @param element Searches the root of element's tree
         * @return The index of element's tree root
         */
	public int find(int element){
		int papa=pere[element]; //la racine
		int pere_adoptif; //le pere du noeud courant
		
		if (papa < 0)
			return element;
		//On parcourt l'arbre pour trouver la racine on la stocke dans papa
		while(pere[papa] >= 0){
			papa = pere[papa];
		}
		//On va mettre la racine comme pere de tous les elements de la composants connexe		
		while(pere[element]!=papa){
			pere_adoptif = pere[element];
			pere[element] = papa;
			element = pere_adoptif;
		}
		return papa;
	}

        /**
         *
         * @param e1 an element of a tree
         * @param e2 an element of a tree
         * @return True if e1's tree and e2's tree has been joined, false if they hasn't ( if e1 and e2 already were in the same tree )
         */
	public boolean union(int e1, int e2){
            if(find(e1) == findOpposite(e2)){
                System.err.print("ERREUR: Le systeme d'equations est faux.\ne"+e1+"  ne doit pas etre oppose a "+e2);
                System.exit(0);
            }
            //rt1 et rt2 sont les racines des arbres dont e1 et e2 sont des éléments
            int rt1 = find(e1);
            int rt2 = find(e2);

            if(rt1==rt2)
                    return false;
            //Si le poids de rt1 est supérieur à celui de rt2 (ce sont des négatifs)
            if (pere[rt1] < pere[rt2] ){
                    //rt1 devient le père de rt2
                    pere[rt2]=rt1;
            }
            //Si ils ont le même poids
            else if (pere[rt1] == pere[rt2]){
                            pere[rt2]=rt1; //rt1 devient le père de rt2
                            pere[rt1]--; //On augmente le poids (toujours des négatifs)
            }
            else{
                    //rt2 devient le père de rt1
                    pere[rt1]=rt2;
            }

            for(int i = 0 ; i < opposite.length ; i++){
                if(i!=find(i))
                    opposite[i] = -1;
                else {
                    if(opposite[i] > -1){
                        opposite[i] = find(opposite[i]);
                        opposite[find(opposite[i])] = i;
                    }
                }
            }

            return true;

	}

        public ArrayList<ArrayList<Ensemble>> getPatates(){
            return patates;
        }

	public int[] getPeres(){
		return pere;
	}

	public int[] getOpposite(){
            return opposite;
        }

        /**
         * This function gets from the set of variables an ArrayList of ArrayList wich allows us to regroup sets of variables with their opposite
         */
        public void getTableau(){
            Ensemble e1 = null;
            ArrayList<Ensemble> temp = new ArrayList<Ensemble>();
            ArrayList<ArrayList<Ensemble>> res = new ArrayList<ArrayList<Ensemble>>();
            boolean passe = false;
            
            for(int i = 0 ; i < pere.length ; i++){
                //Si on trouve une racine
                if(pere[i] < 0){
                    // Dans indiceEnsemble on met l'indice de la liste ou sera stockee l'ensemble auquel appartient la racine
                    indiceEnsemble[i] = temp.size();
                    
                    //On ajoute ensuite une nouvelle liste contenant 1 seul element (la racine) a notre liste
                    e1 = new Ensemble();
                    e1.addElement(i);
                    temp.add(e1);
                }
            }

            for(int i = 0 ; i < pere.length ; i++){
                if(pere[i] >= 0){
                    
                    // On ajoute un element a l'ensemble auquel sa racine appartient deja
                    temp.get(indiceEnsemble[pere[i]]).addElement(i);
                    // Son indice est le meme que celui de sa racine
                    indiceEnsemble[i] = indiceEnsemble[pere[i]];
                }
            }

            int compteur = 1;
            //Avec ce parcours on va lier les ensembles opposes
            for(Ensemble e : temp){
                for(ArrayList<Ensemble> couple : res){
                    if(couple.contains(e)){
                        passe = true;
                    }
                }
                if(!passe){
                    ArrayList<Ensemble> coupleActuel = new ArrayList<Ensemble>();

                    //Ici on va faire un traitement special pour les patates "seules" qui n'ont pas d'oppose
                    //Et sinon on va tester la taille des patates pour mettre le plus grosse "en haut"
                    if(opposite[e.getElement(0)] > -1){
                        Ensemble courant = temp.get(indiceEnsemble[opposite[e.getElement(0)]]);
                        if(e.size() > temp.get(indiceEnsemble[opposite[e.getElement(0)]]).size()){
                            coupleActuel.add(e);
                            coupleActuel.add(courant);
                        }
                        else{
                            coupleActuel.add(courant);
                            coupleActuel.add(e);
                        }
                        
                    }
                    else{
                        coupleActuel.add(e);
                    }
                    //Dans cette boucle on parcourt indiceEnsemble pour mettre a jour les indices si l'element est dans la patate du haut ou du bas
                    for(int i = 0 ; i <  indiceEnsemble.length ; i++){
                        if (coupleActuel.get(0).contains(i))
                            indiceEnsemble[i] = compteur;
                        else if (coupleActuel.size() > 1 && coupleActuel.get(1).contains(i))
                            indiceEnsemble[i] = -compteur;

                    }
                    res.add(coupleActuel);
                    compteur++;
                }
                passe = false;
            }
            patates = res;
        }

        /**
         * This function make the enumeration of sums from the array "soustractions" then it displays it
         */
        public void makeEnum(){
            soustractions = new int[patates.size()];

            ArrayList<Integer> list = new ArrayList<Integer>();
            
            //Dans cette boucle, on va mettre dans le tableau soustractions, la difference entre le nombre d'elements des patates du haut et de celles du bas
            for(int i = 0 ; i < soustractions.length ; i++){
                ArrayList<Ensemble> coupleCourant = patates.get(i);
                soustractions[i] = (coupleCourant.size() > 1) ? (coupleCourant.get(0).size() - coupleCourant.get(1).size()) : coupleCourant.get(0).size();
                list.add(soustractions[i]);
            }

            //Apres avoir obtneu le tableau des soustractions, on recupere le tableau des booleens de l'enumeration des sommes
            Enumeration e = new Enumeration(list);
            ArrayList<Somme> res = e.getResult();

            // On est oblige de calculer d'abord l'enumeration a 0 et son poids a la main puis on l'ajoute dans la liste des Somme que on nous renvoie
            ArrayList<ArrayList<Integer>> resultat = new ArrayList<ArrayList<Integer>>();

            int poids = 0;
            for(ArrayList<Ensemble> pat : patates){
                if(pat.size() > 1){
                    poids += pat.get(1).size();
                }
                else{
                    poids += pat.get(0).size();
                }

            }

            Somme s2 = new Somme(patates.size(),poids);

            res.add(0,s2);

            //Maintenant on va traiter les enumerations renvoyees pour pouvoir afficher a quelles varialbes elles correspondent
            for(Somme s : res){
                ArrayList<Integer> result = new ArrayList<Integer>();
                boolean[] tab = s.getTab();
                for(int i = 0 ; i < indiceEnsemble.length ; i++){
                    result.add(0);
                    if(indiceEnsemble[i] < 0){
                        if(!tab[-indiceEnsemble[i]-1])
                            result.set(i, 1);
                    }
                    else{
                        if(tab[indiceEnsemble[i]-1])
                            result.set(i, 1);
                    }
                }
                resultat.add(result);
            }

            System.out.print("Resultats ! ");
            for(ArrayList<Integer> l : resultat){
                System.out.println();
                for(Integer i : l){
                    System.out.print(i+" ");
                }
            }
        }


        /**
         * Reset the array pere by setting -1 in eache case
         */
	public void reset(){
		for(int i = 0 ; i < pere.length ; i++){
			pere[i]=-1;
		}
	}
	
}
